package Leetcode100Hot;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/*
戳气球
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
示例 2：
输入：nums = [1,5]
输出：10

提示：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
 */
public class _40戳气球 {

    @Test
    public void test(){
        System.out.println(maxCoins(new int[]{1,5}));
    }


    //WA 9/73
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int res = 0;
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(nums[i]);
        }
        while (!arr.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int minIndex = 0;
            int size = arr.size();
            for (int i = 0; i < size; i++) {
                int pred = i == 0 ? 1 : arr.get(i - 1);
                int tail = i == size - 1 ? 1 : arr.get(i + 1);
                int num = pred * tail * arr.get(i);
                list.add(num);
                minIndex = Math.min(arr.get(minIndex),arr.get(i)) == arr.get(i) ? i : minIndex;
            }
            Integer remove = 0;
            if (size != 3){
                remove = list.remove(minIndex);
                arr.remove(minIndex);
            }else {
                remove = list.remove(1);
                arr.remove(1);
            }
            res += remove;
        }
        return res;
    }

    //官解：方法一：记忆化搜索
    /*
    https://leetcode.cn/problems/burst-balloons/solutions/2555834/da-bai-hua-jiang-dpsi-lu-tong-su-yi-dong-3ph7/
    */
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/burst-balloons/solutions/336390/chuo-qi-qiu-by-leetcode-solution/
     */
    class Solution {
        public int[][] rec;
        public int[] val;

        public int maxCoins(int[] nums) {
            int n = nums.length;
            val = new int[n + 2];
            for (int i = 1; i <= n; i++) {
                val[i] = nums[i - 1];
            }
            val[0] = val[n + 1] = 1;
            rec = new int[n + 2][n + 2];
            for (int i = 0; i <= n + 1; i++) {
                Arrays.fill(rec[i], -1);
            }
            return solve(0, n + 1);
        }

        public int solve(int left, int right) {
            if (left >= right - 1) {
                return 0;
            }
            if (rec[left][right] != -1) {
                return rec[left][right];
            }
            for (int i = left + 1; i < right; i++) {
                int sum = val[left] * val[i] * val[right];
                sum += solve(left, i) + solve(i, right);
                rec[left][right] = Math.max(rec[left][right], sum);
            }
            return rec[left][right];
        }
    }


}
